package com.jxm.graph;

import com.jxm.tree.UF_Tree_Weighted;

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * @Author: jxm
 * @Description: 并查集 案例-畅通工程
 * @Date: 2022/7/29 16:35
 * @Version: 1.0
 */
public class Traffic_Project_2 {

    public static void main(String[] args) throws Exception {
        //构建一个缓冲读取流BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(Traffic_Project_2.class.getClassLoader().getResourceAsStream("traffic_project.txt")));

        //读取第一行数据20
        int totalNum = Integer.parseInt(br.readLine());

        //构建一个Graph对象
        Graph G = new Graph(totalNum);
        //读取第二行数据7
        int roadNum = Integer.parseInt(br.readLine());
        //循环读取有限次（7），读取已经修建好的道路
        for (int i = 0; i < roadNum; i++) {
            String line = br.readLine();
            String[] split = line.split(" ");
            int v = Integer.parseInt(split[0]);
            int w = Integer.parseInt(split[1]);
            //调用图的addEdge方法，把边添加到图中，表示已经修建好的道路
            G.addEdge(v,w);
        }

        //构建一个深度优先搜索对象，起点设置为顶点9
        DepthFirstSearch search = new DepthFirstSearch(G, 9);
        //调用marked方法，判断8顶点和10顶点是否与起点9相通
        System.out.println("判断8顶点:"+search.marked(8));
        System.out.println("判断10顶点:"+search.marked(10));

    }
}
